﻿#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <algorithm>
#include <mutex>
#include <atomic>
#include <Windows.h>
#include <unordered_map>
#include "ObjectPool.h"
using std::cout;
using std::endl;

#ifdef _WIN32
#include <windows.h>
#else
// ...
#endif



// ⼩于等于MAX_BYTES，就找thread cache申请,256KB
// ⼤于MAX_BYTES，就直接找page cache或者系统堆申请
static const size_t MAX_BYTES = 256*1024;  
// thread cache 和 central cache⾃由链表哈希桶的表⼤⼩
static const size_t NFREELISTS = 208;
// page cache 管理span list哈希表⼤⼩ //page cache中哈希桶的个数
static const size_t NPAGES = 129;   //因为pagecache的哈希桶映射规则采用的是直接定址法，比如1号桶挂的都是1页的span，2号桶挂的都是2页的span
									//不存在页，因此从1号桶开始，128+1=129
// ⻚⼤⼩转换偏移, 即⼀⻚定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13;    //页号*8*1024
#ifdef _WIN64 //64位既有32也有64的定义，32位只有32；因此避免64位识别成为32，_win64放前面
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif 

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE,PAGE_READWRITE);
#else
		// linux下brk mmap等
#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr,0, MEM_RELEASE);
#else
	// linux下brk mmap等
#endif
}


static void* &NextObj(void* obj)
{
	return *(void**)obj;
}
class FreeList //对哈希桶上节点自由链表的插入和取出
{				//管理切分好的小对象的自由链表
public:
	void Push(void* obj)
	{
		assert(obj);
		//*(void**)obj=_freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}
	//插入一段范围的对象到自由链表
	void PushRange(void* start,void* end,size_t n) //一段范围的对象
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}
	void* Pop()
	{
		assert(_freeList);
		void* obj = _freeList;
		//_freeList = *(void**)obj;
		_freeList = NextObj(obj);
		
		--_size;
		return obj;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n-1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);//自由链表指向end的下一个对象
		NextObj(end) = nullptr;//取出的一段链表的表尾置空
		_size -= n;
	}
	bool Empty()
	{
		return _freeList == nullptr;//自由链表
	}
	size_t& MaxSize() //公有成员函数用于获取这个变量
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList=nullptr; //自由链表
	size_t _maxSize = 1;
	size_t _size=0;
};

class SizeClass
{
public:
	    // 整体控制在最多10 % 左右的内碎⽚浪费
		// [1,128]				8byte对⻬		freelist[0,16)
		// [128+1,1024]			16byte对⻬		freelist[16,72)
		// [1024+1,81024]		128byte对⻬		freelist[72,128)
		// [8*1024+1,641024]	1024byte对⻬	freelist[128,184)
		// [64*1024+1,256*1024] 8*1024byte对⻬	freelist[184,208)
	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		return ((bytes + align - 1) & ~(align - 1));
	}
	static inline size_t RoundUp(size_t bytes)
	{
		//进行哈希桶的对齐，计算对齐大小
		if (bytes <= 128) {
			return _RoundUp(bytes, 8);
		}
		else if(bytes<=1024){
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8*1024) {
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024) {
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024) {
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			//大于256KB的按页对齐
			return _RoundUp(bytes,1<<PAGE_SHIFT);

		}
		
	}
	//static inline size_t _Index(size_t bytes, size_t align_shift)
	//{	
	//	if (bytes % align_shift == 0)	//8,16,24,32....,桶依次此为0，1，2，3.....
	//	{
	//		return bytes / align_shift - 1;
	//	}
	//	else
	//	{
	//		return bytes / align_shift;  //1234567，都为0，9,10,11,12,13,14,15为1号桶
	//	}
	//}//自己的方法
	static inline size_t _Index(size_t bytes, size_t align_shift) 
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	//计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		//获取是哪个桶
		assert(bytes <= MAX_BYTES);
		//每个区间有多少个链
		static int groups_array[4] = { 16,56,56,56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if(bytes <= 1024)
		{
			return _Index(bytes-128, 4)+groups_array[0]; //因为不会从下标零再开始，所以加上前面的桶的个数就是正确的下标
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes-1024, 7)+groups_array[0]+groups_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes-8*1024, 10) + groups_array[0] + groups_array[1] + groups_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes-64*1024, 13) + groups_array[0] + groups_array[1] + groups_array[2]+groups_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}
	//thread cache一次从central cache获取对象的上限
	static size_t NumMoveSize(size_t size)
	{
		//thread cache要申请的对象再小，我最多也就给512个对象，越大，我最少一次性也给两个对象
		assert(size > 0);

		//对象越小，计算出的上限越高
		//对象越大，计算出的上限越低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;

		return num;
	}
	// 计算⼀次向系统获取⼏个⻚
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}

};

struct Span
{ 

	//size_t _page_Id; 32位可以，2^32/2^13个页，64位超出范围，2^64/2^13；
	PAGE_ID _page_Id=0;  //大块内存的起始页号
	size_t _n=0;	//页数量

	Span* _next=nullptr; //双向链表的结构
	Span* _prev=nullptr;

	size_t _objSize = 0;  // 切好的小对象的大小
	size_t _useCount=0; //切好小块内存，被分配给thread_cache的计数
	void* _freeList=nullptr; //切好的小块内存的自由链表

	bool _isuse = false; //标记这个span是否正在被使用
};
class SpanList  //central cache的每个哈希桶里面存储的都是一个双链表结构
{
public:
	SpanList() 
	{
		static ObjectPool<Span> _spanPool;
		_head = _spanPool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span* pos)   //从双链表删除的Span，会还给下一层的page cache,相当于就是移除span，因此不需要进行delete操作
	{
		assert(pos);
		assert(pos != _head);//不能删除哨兵位的头结点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	//~SpanList(); 定义未实现,链接器找不到对应的实现。LNK2019	无法解析的外部符号
	~SpanList()
	{}

private:
	Span* _head;
public:
	std::mutex _mtx;  //桶锁
};
